Facetedpedia enabling query%2Ddependent faceted search for wikipedia.

Turbo%2Dcharging hidden database samplers with overflowing queries and skew reduction.

Algorithm%2Dsafe privacy%2Dpreserving data publishing.

Versatile publishing for privacy preservation.



Constructing and exploring composite items.
Nowadays, online shopping has become a daily activity. Web users purchase a variety of items ranging from books to electronics. The large supply of online products calls for sophisticated techniques to help users explore available items. We propose to build composite items which associate a central item with a set of packages, formed by satellite items, and help users explore them. For example, a user shopping for an iPhone (i.e., the central item) with a price budget can be presented with both the iPhone and a package of other items that match well with the iPhone (e.g., {Belkin case, Bose sounddock, Kroo USB cable}) as a composite item, whose total price is within the user’s budget. We define and study the problem of effective construction and exploration of large sets of packages associated with a central item, and design and implement efficient algorithms for solving the problem in two stages: summarization, a technique which picks k representative packages for each central item; and visual effect optimization, which helps the user find diverse composite items quickly by minimizing overlap between packages presented to the user in a ranked order. We conduct an extensive set of experiments on Yahoo! Shopping 1 data sets to demonstrate the efficiency and effectiveness of our algorithms.
Unbiased estimation of size and other aggregates over hidden web databases.

Mining Time Series Data.
The last decade has witnessed a tremendous growths of interests in applications that deal with querying and mining of time series data. Numerous representation methods for dimensionality reduction and similarity measures geared towards time series have been introduced. Each individual work introducing a particular method has made specific claims and, aside from the occasional theoretical justifications, provided quantitative experimental observations. However, for the most part, the comparative aspects of these experiments were too narrowly focused on demonstrating the benefits of the proposed methods over some of the previously introduced ones. In order to provide a comprehensive validation, we conducted an extensive set of time series experiments re-implementing 8 different representation methods and 9 similarity measures and their variants, and testing their effectiveness on 38 time series data sets from a wide variety of application domains. In this paper, we give an overview of these different techniques and present our comparative experimental findings regarding their effectiveness. Our experiments have provided both a unified validation of some of the existing achievements, and in some cases, suggested that certain claims in the literature may be unduly optimistic. 1.
Facetedpedia dynamic generation of query%2Ddependent faceted interfaces for wikipedia.
This paper proposes Facetedpedia, a faceted retrieval system for information discovery and exploration in Wikipedia. Given the set of Wikipedia articles resulting from a keyword query, Facetedpedia generates a faceted interface for navigating the result articles. Compared with other faceted retrieval systems, Facetedpedia is fully automatic and dynamic in both facet generation and hierarchy construction, and the facets are based on the rich semantic information from Wikipedia. The essence of our approach is to build upon the collaborative vocabulary in Wikipedia, more specifically the intensive internal structures (hyperlinks) and folksonomy (category system). Given the sheer size and complexity of this corpus, the space of possible choices of faceted interfaces is prohibitively large. We propose metrics for ranking individual facet hierarchies by user’s navigational cost, and metrics for ranking interfaces (each with 
Mining Time Series Data.
The last decade has witnessed a tremendous growths of interests in applications that deal with querying and mining of time series data. Numerous representation methods for dimensionality reduction and similarity measures geared towards time series have been introduced. Each individual work introducing a particular method has made specific claims and, aside from the occasional theoretical justifications, provided quantitative experimental observations. However, for the most part, the comparative aspects of these experiments were too narrowly focused on demonstrating the benefits of the proposed methods over some of the previously introduced ones. In order to provide a comprehensive validation, we conducted an extensive set of time series experiments re-implementing 8 different representation methods and 9 similarity measures and their variants, and testing their effectiveness on 38 time series data sets from a wide variety of application domains. In this paper, we give an overview of these different techniques and present our comparative experimental findings regarding their effectiveness. Our experiments have provided both a unified validation of some of the existing achievements, and in some cases, suggested that certain claims in the literature may be unduly optimistic. 1.
An Access Cost%2DAware Approach for Object Retrieval over Multiple Sources.
Source and object selection and retrieval from large multi-source data sets are fundamental operations in many applications. In this paper, we initiate research on efficient source (e.g., database) and object selection algorithms on large multi-source data sets. Specifically, in order to acquire a specified number of satisfying objects with minimum cost over multiple databases, the query engine needs to determine the access overhead for individual data sources, the overhead of retrieving objects from each source, and possibly other statistics such as estimating the frequency of finding a satisfying object in order to determine how many objects to retrieve from each data source. We adopt a probabilistic approach to source selection utilizing a cost structure and a dynamic programming model for computing the optimal number of objects to retrieve from each data source. Such a structure can be a valuable asset where there is a monetary or time related cost associated with accessing large distributed databases. We present a thorough experimental evaluation to validate our techniques using real-world data sets. 1.
Space efficiency in group recommendation.

TRANS Top%2Dk Implementation Techniques of Minimum Effort Driven Faceted Search For Databases.

Ranking objects based on relationships and fixed associations.
Text corpora are often enhanced by additional metadata which relate real-world entities, with each document in which such entities are discussed. Such relationships are typically obtained through widely available Information Extraction tools. At the same time, interesting known associations typically hold among these entities. For instance, a corpus might contain discussions on hotels, cities and airlines; fixed associations among these entities may include: airline A operates a flight to city C, hotel H is located in city C. A plethora of applications necessitate the identification of associated entities, each best matching a given set of keywords. Consider the sample query: Find a holiday package in a “pet-friendly ” hotel, located in a “historical ” yet “lively ” city, with travel operated by an “economical ” and “safe ” airline. These keywords are unlikely to occur in the textual description of entities themselves, (e.g., the actual hotel name or the city name or the airline name). Consequently to answer such queries, one needs to exploit both relationships between entities and documents (e.g., keyword “pet-friendly ” occurs in a document that contains an entity specifying a hotel name H), and the known associations between entities (e.g., hotel H is located in city C). In this work, we focus on the class of “entity package finder” queries outlined above. We demonstrate that existing techniques cannot be efficiently adapted to solve this problem, as the resulting algorithm relies on estimations with excessive runtime and/or storage overheads. We propose an efficient algorithm to process such queries, over large corpora. We devise early pruning and termination strategies, in the presence of joins and aggregations (executed on entities extracted from text), that do not depend on any estimates. Our analysis and experimental evaluation on real and synthetic data demonstrates the efficiency and scalability of our approach. 1.
Top%2Dk Algorithms and Applications.
In this paper we introduce the distributed spatio-temporal similarity search problem: given a query trajectory Q, we want to find the trajectories that follow a motion similar to Q, when each of the target trajectories is segmented across a number of distributed nodes. We propose two novel algorithms, UB-K and UBLB-K, which combine local computations of lower and upper bounds on the matching between the distributed subsequences and Q. Such an operation generates the desired result without pulling together all the distributed subsequences over the fundamentally expensive communication medium. Our solutions find applications in a wide array of domains, such as cellular networks, wildlife monitoring and video surveillance. Our experimental evaluation using realistic data demonstrates that our framework is both e#cient and robust to a variety of conditions.
Ranking objects based on relationships and fixed associations.
Text corpora are often enhanced by additional metadata which relate real-world entities, with each document in which such entities are discussed. Such relationships are typically obtained through widely available Information Extraction tools. At the same time, interesting known associations typically hold among these entities. For instance, a corpus might contain discussions on hotels, cities and airlines; fixed associations among these entities may include: airline A operates a flight to city C, hotel H is located in city C. A plethora of applications necessitate the identification of associated entities, each best matching a given set of keywords. Consider the sample query: Find a holiday package in a “pet-friendly ” hotel, located in a “historical ” yet “lively ” city, with travel operated by an “economical ” and “safe ” airline. These keywords are unlikely to occur in the textual description of entities themselves, (e.g., the actual hotel name or the city name or the airline name). Consequently to answer such queries, one needs to exploit both relationships between entities and documents (e.g., keyword “pet-friendly ” occurs in a document that contains an entity specifying a hotel name H), and the known associations between entities (e.g., hotel H is located in city C). In this work, we focus on the class of “entity package finder” queries outlined above. We demonstrate that existing techniques cannot be efficiently adapted to solve this problem, as the resulting algorithm relies on estimations with excessive runtime and/or storage overheads. We propose an efficient algorithm to process such queries, over large corpora. We devise early pruning and termination strategies, in the presence of joins and aggregations (executed on entities extracted from text), that do not depend on any estimates. Our analysis and experimental evaluation on real and synthetic data demonstrates the efficiency and scalability of our approach. 1.
DynaCet Building Dynamic Faceted Search Systems over Databases.
Abstract — Extracting information and insights from large databases is a time-consuming activity and has received considerable research attention recently. In this demo, we present DynaCet- a domain independent system that provides effective minimum-effort based dynamic faceted search solutions over enterprise databases. At every step, Dynacet suggests facets depending on the user response in the previous step. Facets are selected based on their ability to rapidly drill down to the most promising tuples, as well as on the ability of the user to provide desired values for them. The benefits provided include faster access to information stored in databases while taking into consideration the variance in user knowledge and preferences. I.
Leveraging COUNT Information in Sampling Hidden Databases.

Privacy risks in health databases from aggregate disclosure.

HDSampler revealing data behind web form interfaces.
A large number of online databases are hidden behind the web. Users to these systems can form queries through web forms to retrieve a small sample of the database. Sampling such hidden databases is widely desired for understanding the nature and quality of data stored in them. We have developed HDSampler, which to the best of our knowledge is the first practical system for sampling structured hidden web databases. It enables efficient sampling of the databases and accurate answering of aggregate queries, to provide analysts with valuable information for data analytics, as well as help power a multitude of third-party applications such as web-mashups and meta-search engines. For the purpose of this demo, we present an instance of HDSampler on Google Base- a content-rich hidden web database maintained by Google. By using HDSampler, the demo reveals a snapshot of the marginal distribution of various attributes of Google Base in a matter of minutes.
Privacy preservation of aggregates in hidden databases why and how%3F
Many websites provide form-like interfaces which allow users to execute search queries on the underlying hidden databases. In this paper, we explain the importance of protecting sensitive aggregate information of hidden databases from being disclosed through individual tuples returned by the search queries. This stands in contrast to the traditional privacy problem where individual tuples must be protected while ensuring access to aggregating information. We propose techniques to thwart bots from sampling the hidden database to infer aggregate information. We present theoretical analysis and extensive experiments to illustrate the effectiveness of our approach. Categories and Subject Descriptors
Determining Attributes to Maximize Visibility of Objects.
In recent years, there has been significant interest in the development of ranking functions and efficient top-k retrieval algorithms to help users in ad-hoc search and retrieval in databases (e.g., buyers searching for products in a catalog). We introduce a complementary problem: how to guide a seller in selecting the best attributes of a new tuple (e.g., a new product) to highlight so that it stands out in the crowd of existing competitive products and is widely visible to the pool of potential buyers. We develop several formulations of this problem. Although the problems are NP-complete, we give several exact and approximation algorithms that work well in practice. One type of exact algorithms is based on Integer Programming (IP) formulations of the problems. Another class of exact methods is based on maximal frequent itemset mining algorithms. The approximation algorithms are based on greedy heuristics. A detailed performance study illustrates the benefits of our methods on real and synthetic data. 
Determining Attributes to Maximize Visibility of Objects.
In recent years, there has been significant interest in the development of ranking functions and efficient top-k retrieval algorithms to help users in ad-hoc search and retrieval in databases (e.g., buyers searching for products in a catalog). We introduce a complementary problem: how to guide a seller in selecting the best attributes of a new tuple (e.g., a new product) to highlight so that it stands out in the crowd of existing competitive products and is widely visible to the pool of potential buyers. We develop several formulations of this problem. Although the problems are NP-complete, we give several exact and approximation algorithms that work well in practice. One type of exact algorithms is based on Integer Programming (IP) formulations of the problems. Another class of exact methods is based on maximal frequent itemset mining algorithms. The approximation algorithms are based on greedy heuristics. A detailed performance study illustrates the benefits of our methods on real and synthetic data. 
Measure%2Ddriven Keyword%2DQuery Expansion.
User generated content has been fueling an explosion in the amount of available textual data. In this context, it is also common for users to express, either explicitly (through numerical ratings) or implicitly, their views and opinions on products, events, etc. This wealth of textual information necessitates the development of novel searching and data exploration paradigms. In this paper we propose a new searching model, similar in spirit to faceted search, that enables the progressive refinement of a keywordquery result. However, in contrast to faceted search which utilizes domain-specific and hard-to-extract document attributes, the refinement process is driven by suggesting interesting expansions of the original query with additional search terms. Our query-driven and domain-neutral approach employs surprising word co-occurrence patterns and (optionally) numerical user ratings in order to identify meaningful top-k query expansions and allow one to focus on a particularly interesting subset of the original result set. The proposed functionality is supported by a framework that is computationally efficient and nimble in terms of storage requirements. Our solution is grounded on Convex Optimization principles that allow us to exploit the pruning opportunities offered by the natural top-k formulation of our problem. The performance benefits offered by our solution are verified using both synthetic data and large real data sets comprised of blog posts. 1.
Group Recommendation Semantics and Efficiency.
We study the problem of group recommendation. Recommendation is an important information exploration paradigm that retrieves interesting items for users based on their profiles and past activities. Single user recommendation has received significant attention in the past due to its extensive use in Amazon and Netflix. How to recommend to a group of users who may or may not share similar tastes, however, is still an open problem. The need for group recommendation arises in many scenarios: a movie for friends to watch together, a travel destination for a family to spend a holiday break, and a good restaurant for colleagues to have a working lunch. Intuitively, items that are ideal for recommendation to a group may be quite different from those for individual members. In this paper, we analyze the desiderata of group recommendation and propose a formal semantics that accounts for both item relevance to a group and disagreements among group members. We design and implement algorithms for efficiently computing group recommendations. We evaluate our group recommendation method through a comprehensive user study conducted on Amazon Mechanical Turk and demonstrate that incorporating disagreements is critical to the effectiveness of group recommendation. We further evaluate the efficiency and scalability of our algorithms on the MovieLens data set with 10M ratings. 1.
Improved Search for Socially Annotated Data.
Social annotation is an intuitive, on-line, collaborative process through which each element of a collection of resources (e.g., URLs, pictures, videos, etc.) is associated with a group of descriptive keywords, widely known as tags. Each such group is a concise and accurate summary of the relevant resource’s content and is obtained via aggregating the opinion of individual users, as expressed in the form of short tag sequences. The availability of this information gives rise to a new searching paradigm where resources are retrieved and ranked based on the similarity of a keyword query to their accompanying tags. In this paper, we present a principled and efficient search and resource ranking methodology that utilizes exclusively the userassigned tag sequences. Ranking is based on solid probabilistic foundations and our growing understanding of the dynamics and structure of the social annotation process, which we capture by employing powerful interpolated n-gram models on the tag sequences. The efficiency and applicability of the proposed solution to large data sets is guaranteed through the introduction of a novel and highly scalable constrained optimization framework, employed both for training and incrementally maintaining the n-gram models. We experimentally validate the efficiency and effectiveness of our solutions compared to other applicable approaches. Our evaluation is based on a large crawl of del.icio.us, numbering hundreds of thousands of users and millions of resources, thus demonstrating the applicability of our solutions to real-life, large scale systems. In particular, we demonstrate that the use of interpolated n-grams for modeling tag sequences results in superior ranking effectiveness, while the proposed optimization framework is superior in terms of performance both for obtaining ranking parameters and incrementally maintaining them. 1.
Keyword querying and Ranking in Databases.

Anytime measures for top%2Dk algorithms on exact and fuzzy data sets.
 
Proceedings of the 14th International Conference on Management of Data

Minimum%2Deffort driven dynamic faceted search in structured databases.
In this paper, we propose minimum-effort driven navigational techniques for enterprise database systems based on the faceted search paradigm. Our proposed techniques dynamically suggest facets for drilling down into the database such that the cost of navigation is minimized. At every step, the system asks the user a question or a set of questions on different facets and depending on the user response, dynamically fetches the next most promising set of facets, and the process repeats. Facets are selected based on their ability to rapidly drill down to the most promising tuples, as well as on the ability of the user to provide desired values for them. Our facet selection algorithms also work in conjunction with any ranked retrieval model where a ranking function imposes a bias over the user preferences for the selected tuples. Our methods are principled as well as efficient, and our experimental study validates their effectiveness on several application scenarios. Categories and Subject Descriptors H.2.4 [Database Management]: Systems—query processing,
Standing Out in a Crowd Selecting Attributes for Maximum Visibility.
Abstract — In recent years, there has been significant interest in development of ranking functions and efficient top-k retrieval algorithms to help users in ad-hoc search and retrieval in databases (e.g., buyers searching for products in a catalog). In this paper we focus on a novel and complementary problem: how to guide a seller in selecting the best attributes of a new tuple (e.g., new product) to highlight such that it stands out in the crowd of existing competitive products and is widely visible to the pool of potential buyers. We develop several interesting formulations of this problem. Although these problems are NPcomplete, we can give several exact algorithms as well as approximation heuristics that work well in practice. Our exact algorithms are based on Integer Programming (IP) formulations of the problems, as well as on adaptations of maximal frequent itemset mining algorithms, while our approximation algorithms are based on greedy heuristics. We conduct a performance study illustrating the benefits of our methods on real as well as synthetic data.
Region Sampling Continuous Adaptive Sampling on Sensor Networks.
Abstract — Satisfying energy constraints while meeting performance requirements is a primary concern when a sensor network is being deployed. Many recent proposed techniques offer error bounding solutions for aggregate approximation but cannot guarantee energy spending. Inversely, our goal is to bound the energy consumption while minimizing the approximation error. In this paper, we propose an online algorithm, Region Sampling, for computing approximate aggregates while satisfying a pre-defined energy budget. Our algorithm is distinguished by segmenting a sensor network into partitions of non-overlapping regions and performing sampling and local aggregation for each region. The sampling energy cost rate and sampling statistics are collected and analyzed to predict the optimal sampling plan. Comprehensive experiments on real-world data sets indicate that our approach is at a minimum of 10 % more accurate compared with the previously proposed solutions. I.
Distinct value estimation on peer%2Dto%2Dpeer networks.
Peer-to-Peer networks have become very popular on the Internet, with millions of peers all over the world sharing large volumes of data. In the assistive healthcare sector, it is likely that P2P networks will develop that interconnect and allow the controlled sharing of patient databases of various hospitals, clinics, and research laboratories. However, the sheer scale of these networks has made it difficult to gather statistics that could be used for building new features. In this paper, we present a technique to obtain estimations of the number of distinct values matching a query on the network. We evaluate the technique experimentally and provide a set of results that demonstrate its effectiveness, as well as its flexibility in supporting a variety of queries and applications. 1.
Categorical skylines for streaming data.
The problem of skyline computation has attracted considerable research attention. In the categorical domain the problem becomes more complicated, primarily due to the partially-ordered nature of the attributes of tuples. In this paper, we initiate a study of streaming categorical skylines. We identify the limitations of existing work for offline categorical skyline computation and realize novel techniques for the problem of maintaining the skyline of categorical data in a streaming environment. In particular, we develop a lightweight data structure for indexing the tuples in the streaming buffer, that can gracefully adapt to tuples with many attributes and partially ordered domains of any size and complexity. Additionally, our study of the dominance relation in the dual space allows us to utilize geometric arrangements in order to index the categorical skyline and efficiently evaluate dominance queries. Lastly, a thorough experimental study evaluates the efficiency of the proposed techniques.
Efficient sampling of information in social networks.

The Discrete Basis Problem.
We consider the Discrete Basis Problem, which can be described as follows: given a collection of Boolean vectors find a collection of k Boolean basis vectors such that the original vectors can be represented using disjunctions of these basis vectors. We show that the decision version of this problem is NP-complete and that the optimization version cannot be approximated within any finite ratio. We also study two variations of this problem, where the Boolean basis vectors must be mutually otrhogonal. We show that the other variation is closely related with the well-known Metric k-median Problem in Boolean space. To solve these problems, two algorithms will be presented. One is designed for the variations mentioned above, and it is solely based on solving the k-median problem, while another is a heuristic intended to solve the general Discrete Basis Problem. We will also study the results of extensive experiments made with these two algorithms with both synthetic and real-world data. The results are twofold: with the synthetic data, the algorithms did rather well, but with the real-world data the results were not as good.
Analyzing the Structure and Evolution of Massive Telecom Graphs.
Abstract — With ever growing competition in telecommunications markets, operators have to increasingly rely on business intelligence to offer the right incentives to their customers. Existing approaches for telecom business intelligence have almost solely focused on the individual behavior of customers. In this paper, we use the Call Detail Records of a mobile operator to construct Call graphs, that is, graphs induced by people calling each other. We determine the structural properties of these graphs and also introduce the Treasure-Hunt model to describe the shape of mobile call graphs. We also determine how the structure of these call graphs evolve over time. Finally, since Short Messaging Service (SMS) is becoming a preferred mode of communication among many sections of the society we also study the properties of the SMS graph. Our analysis indicates several interesting similarities as well as differences between the SMS graph and the corresponding call graph. We believe that our analysis techniques can allow telecom operators to better understand the social behavior of their customers, and potentially provide major insights for designing effective incentives.
STAR A System for Tuple and Attribute Ranking of Query Answers.

An Integrated Development Environment for Web Service Composition.

A random walk approach to sampling hidden databases.
I would like to thank my advisor, Dr. Gautam Das, for his constant guidance and support, and for giving me a wonderful opportunity to work on such a challenging project, which involved in depth knowledge of probability and statistics, and also for discussing various practical and interesting aspects of the problem in hand. committee. I am also grateful to Dr. Nan Zhang and Dr. Leonidas Fegaras for serving on my I would also like to thank my parents and brother who have always been a source of inspiration, and all my friends for their constant help and support for this project and throughout my academic career. ii
Ad%2Dhoc Top%2Dk Query Answering for Data Streams.
A top-k query retrieves the k highest scoring tuples from a data set with respect to a scoring function defined on the attributes of a tuple. The efficient evaluation of top-k queries has been an active research topic and many different instantiations of the problem, in a variety of settings, have been studied. However, techniques developed for conventional, centralized or distributed databases are not directly applicable to highly dynamic environments and on-line applications, like data streams. Recently, techniques supporting top-k queries on data streams have been introduced. Such techniques are restrictive however, as they can only efficiently report top-k answers with respect to a pre-specified (as opposed to ad-hoc) set of queries. In this paper we introduce a novel geometric representation for the top-k query problem that allows us to raise this restriction. Utilizing notions of geometric arrangements, we design and analyze algorithms for incrementally maintaining a data set organized in an arrangement representation under streaming updates. We introduce query evaluation strategies that operate on top of an arrangement data structure that are able to guarantee efficient evaluation for ad-hoc queries. The performance of our core technique is augmented by incorporating tuple pruning strategies, minimizing the number of tuples that need to be stored and manipulated. This results in a main memory indexing technique supporting both efficient incremental updates and the evaluation of ad-hoc top-k queries. A thorough experimental study evaluates the efficiency of the proposed technique. 
Anytime Measures for Top%2Dk Algorithms.
Top-k queries on large multi-attribute data sets are fundamental operations in information retrieval and ranking applications. In this paper, we initiate research on the anytime behavior of top-k algorithms. In particular, given specific top-k algorithms (TA and TA-Sorted) we are interested in studying their progress toward identification of the correct result at any point during the algorithms’ execution. We adopt a probabilistic approach where we seek to report at any point of operation of the algorithm the confidence that the top-k result has been identified. Such a functionality can be a valuable asset when one is interested in reducing the runtime cost of top-k computations. We present a thorough experimental evaluation to validate our techniques using both synthetic and real data sets. 1.
Computing Best Coverage Path in the Presence of Obstacles in a Sensor Field.
Abstract. We study the presence of obstacles in computing BCP(s,t) (Best Coverage Path between two points s and t) in a 2D field under surveillance by sensors. Consider a set of m line segment obstacles and n point sensors on the plane. For any path between s to t, p is the least protected point along the path such that the Euclidean distance between p and its closest sensor is maximum. This distance (the path’s cover value) is minimum for a BCP(s,t). We present two algorithmic results. For opaque obstacles, i.e., which obstruct paths and block sensing capabilities of sensors, computation of BCP(s,t) takesO((m 2 n 2 + n 4)log(mn + n 2)) time and O(m 2 n 2 +n 4)space.Fortransparent obstacles, i.e., which only obstruct paths, but allows sensing, computation of BCP(s, t)takes O(nm 2 + n 3)timeandO(m 2 + n 2) space. We believe, this is one of the first efforts to study the presence of obstacles in coverage problems in sensor networks. 1
Optimized stratified sampling for approximate query processing.
The ability to approximately answer aggregation queries accurately and efficiently is of great benefit for decision support and data mining tools. In contrast to previous sampling-based studies, we treat the problem as an optimization problem where, given a workload of queries, we select a stratified random sample of the original data such that the error in answering the workload queries using the sample is minimized. A key novelty of our approach is that we can tailor the choice of samples to be robust even for workloads that are “similar” but not necessarily identical to the given workload. Finally, our techniques recognize the importance of taking into account the variance in the data distribution in a principled manner. We show how our solution can be implemented on a database system, and present results of extensive experiments on Microsoft SQL Server that demonstrate the superior quality of our method compared to previous work.  
Efficient Approximate Query Processing in Peer%2Dto%2DPeer Networks.

Report on the First International Workshop on Ranking in Databases %28DBRank%2707%29.

Introduction to special issue ACM SIGKDD 2006.

Vulnerabilities of Internet Access Mechanisms from Mobile Ad Hoc Networks.

On the structural properties of massive telecom call graphs findings and implications.

XML Query Routing in Structured P2P Systems.
Abstract. This paper addresses the problem of data placement, indexing, and querying large XML data repositories distributed over an existing P2P service infrastructure. Our architecture scales gracefully to the network and data sizes, is fully distributed, fault tolerant and selforganizing, and handles complex queries efficiently, even those queries that use full-text search. Our framework for indexing distributed XML data is based on both meta-data information and textual content. We introduce a novel data synopsis structure to summarize text that correlates textual with positional information and increases query routing precision. Our processing framework maps an XML query with full-text search into a distributed program that migrates from peer to peer, collecting relevant document locations along the way. In addition, we introduce methods to handle network updates, such as node arrivals, departures, and failures. Finally, we report on a prototype implementation, which is used to validate the accuracy of our data synopses and to analyze the various costs involved in indexing XML data and answering queries. 1
Approximating Aggregation Queries in Peer%2Dto%2DPeer Networks.

The Discrete Basis Problem.
We consider the Discrete Basis Problem, which can be described as follows: given a collection of Boolean vectors find a collection of k Boolean basis vectors such that the original vectors can be represented using disjunctions of these basis vectors. We show that the decision version of this problem is NP-complete and that the optimization version cannot be approximated within any finite ratio. We also study two variations of this problem, where the Boolean basis vectors must be mutually otrhogonal. We show that the other variation is closely related with the well-known Metric k-median Problem in Boolean space. To solve these problems, two algorithms will be presented. One is designed for the variations mentioned above, and it is solely based on solving the k-median problem, while another is a heuristic intended to solve the general Discrete Basis Problem. We will also study the results of extensive experiments made with these two algorithms with both synthetic and real-world data. The results are twofold: with the synthetic data, the algorithms did rather well, but with the real-world data the results were not as good.
Ordering the attributes of query results.
There has been a great deal of interest in the past few years on ranking of results of queries on structured databases, including work on probabilistic information retrieval, rank aggregation, and algorithms for merging of ordered lists. In many applications, for example sales of homes, used cars or electronic goods, data items have a very large number of attributes. When displaying a (ranked) list of items to users, only a few attributes can be shown. Traditionally, these are selected manually. We argue that automatic selection of attributes is required to deal with different requirements of different users. We formulate the problem as an optimization problem of choosing the most “useful ” set of attributes, that is, the attributes that are most influential in the ranking of the items. We discuss different variants of our notion of attribute usefulness, and propose a hybrid Split-Pane approach that returns a composite of the top attributes of each variant. We conduct both a performance and a user study illustrating the benefits of our algorithms in terms of efficiency and quality of explanation. 1.
Answering Top%2Dk Queries Using Views.
There has been considerable past work on efficiently computing top k objects by aggregating information from multiple ranked lists of these objects. An important instance of this problem is query processing in search engines: One has to combine information from several different posting lists (rankings) of web pages (objects) to obtain the top k web pages to answer user queries. Two particularly well-studied approaches to achieve efficiency in top-k aggregation include early-termination algorithms (e.g., TA and NRA) and preaggregation of some of the input lists. However, there has been little work on a rigorous treatment of combining these approaches. We generalize the TA and NRA algorithms to the case when preaggregated intersection lists are available in addition to the original lists. We show that our versions of TA and NRA continue to remain “instance optimal, ” a very strong optimality notion that is a highlight of the original TA and NRA algorithms. Using an index of millions of web pages and real-world search engine queries, we empirically characterize the performance gains offered by our new algorithms. We show that the practical benefits of intersection lists can be fully realized only with an early-termination algorithm.
Probabilistic information retrieval approach for ranking of database query results.
We investigate the problem of ranking the answers to a database query when many tuples are returned. In particular, we present methodologies to tackle the problem for conjunctive and range queries, by adapting and applying principles of probabilistic models from Information Retrieval for structured data. Our solution is domain independent and leverages data and workload statistics and correlations. We evaluate the quality of our approach with a user survey on a real database. Furthermore, we present and experimentally evaluate algorithms to efficiently retrieve the top ranked results, which demonstrate the feasibility of our ranking system.
Distributed core assisted scalable data dissemination in mobile ad hoc networks.

CCID Core construction for information dissemination in ad hoc scenario.

Mining Chains of Relations.
Traditional data mining applications consider the problem of mining a single relation between two attributes. For example, in a scientific bibliography database, authors are related to papers, and we may be interested in discovering association rules between authors. However, in real life, we often have multiple attributes related though chains of relations. For example, authors write papers, and papers concern one or more topics. Mining such relational chains poses additional challenges. In this paper we consider the following problem: given a chain of two relations R1(A, P) and R2(P, T) we want to find selectors for the objects in T such that the projected relation between A and P satisfies a specific property. The motivation for our approach is that a given property might not hold on the whole dataset, but it might hold when projecting the data on a selector set. We discuss various algorithms and we examine the conditions under which the apriori technique can be used. We experimentally demonstrate the effectiveness of our methods. 1
Approximate Query Processing.
Abstract. Approximate query processing has emerged as a cost-effective approach for dealing with the huge data volumes and stringent response-time requirements of today’s decision support systems (DSS). Most work in this area, however, has so far been limited in its query processing scope, typically focusing on specific forms of aggregate queries. Furthermore, conventional approaches based on sampling or histograms appear to be inherently limited when it comes to approximating the results of complex queries over high-dimensional DSS data sets. In this paper, we propose the use of multi-dimensional wavelets as an effective tool for general-purpose approximate query processing in modern, high-dimensional applications. Our approach is based on building wavelet-coefficient synopses of the data and using these synopses to provide approximate answers to queries. We develop novel query processing
Mining Time Series Data.
The last decade has witnessed a tremendous growths of interests in applications that deal with querying and mining of time series data. Numerous representation methods for dimensionality reduction and similarity measures geared towards time series have been introduced. Each individual work introducing a particular method has made specific claims and, aside from the occasional theoretical justifications, provided quantitative experimental observations. However, for the most part, the comparative aspects of these experiments were too narrowly focused on demonstrating the benefits of the proposed methods over some of the previously introduced ones. In order to provide a comprehensive validation, we conducted an extensive set of time series experiments re-implementing 8 different representation methods and 9 similarity measures and their variants, and testing their effectiveness on 38 time series data sets from a wide variety of application domains. In this paper, we give an overview of these different techniques and present our comparative experimental findings regarding their effectiveness. Our experiments have provided both a unified validation of some of the existing achievements, and in some cases, suggested that certain claims in the literature may be unduly optimistic. 1.
Hop counting based lightweight quality of service model for sensor devices.

Proceedings of the 9th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery

Intelligent Information Technology
Abstract: Nowadays, companies seeking to advance their information systems are facing an overwhelming variety of fast pacing innovations in the information technology sector. Many of these innovations could lead to new ways of extending existing competitive advantages or leveraging weaknesses respectively. Furthermore technological progress is characterized by shorter technology life cycles and by discontinuities. The challenge for developing information systems that contribute to a company’s competitive advantage is to gather intelligence information of technological progress, evaluate possible strategic impacts of that information and prepare for decision making. We argue that technologies may be seen as a form of knowledge and therefore propose a pattern based modeling language to capture and model information technologies. We demonstrate the applicability of the modeling language on the example of web service related technologies. 1
Rotation invariant distance measures for trajectories.
For the discovery of similar patterns in 1D time-series, it is very typical to perform a normalization of the data (for example a transformation so that the data follow a zero mean and unit standard deviation). Such transformations can reveal latent patterns and are very commonly used in datamining applications. However, when dealing with multidimensional time-series, which appear naturally in applications such as video-tracking, motion-capture etc, similar motion patterns can also be expressed at different orientations. It is therefore imperative to provide support for additional transformations, such as rotation. In this work, we transform the positional information of moving data, into a space that is translation, scale and rotation invariant. Our distance measure in the new space is able to detect elastic matches and can be efficiently lower bounded, thus being computationally tractable. The proposed methods are easy to implement, fast to compute and can have many applications for real world problems, in areas such as handwriting recognition and posture estimation in motion-capture data. Finally, we empirically demonstrate the accuracy and the efficiency of the technique, using real and synthetic handwriting data.
Probabilistic Ranking of Database Query Results.
We investigate the problem of ranking answers to a database query when many tuples are returned. We adapt and apply principles of probabilistic models from Information Retrieval for structured data. Our proposed solution is domain independent. It leverages data and workload statistics and correlations. Our ranking functions can be further customized for different applications. We present results of preliminary experiments which demonstrate the efficiency as well as the quality of our ranking system. 1.
Summary%2Dbased routing for content%2Dbased event distribution networks.
Abstract — Providing scalable distributed Web-based eventing services has been an important research topic. It is desirable to have an effective mechanism for the servers to summarize their filters for in-network preprocessing in order to optimize system performance. In this paper, we propose a summary-based routing mechanism and introduce the notion of imprecise summaries to provide a trade-off between routing overhead and event traffic. Our system uses similarity-based filter clustering to reduce overall event traffic and performs self-tuning summary precision selection to optimize throughput. We have implemented summary-based routing on top of an XML-based infrastructure that closely follows the proposed Web services standards. Measurements from the actual implementation validate our analytical and simulation results, and demonstrate the practical benefits of the proposed techniques. I.
Automated Ranking of Database Query Results.
We investigate the problem of ranking answers to a database query when many tuples are returned. We adapt and apply principles of probabilistic models from Information Retrieval for structured data. Our proposed solution is domain independent. It leverages data and workload statistics and correlations. Our ranking functions can be further customized for different applications. We present results of preliminary experiments which demonstrate the efficiency as well as the quality of our ranking system. 1.
Dynamic Sample Selection for Approximate Query Processing.

DBXplorer A System for Keyword%2DBased Search over Relational Databases.
Internet search engines have popularized the keywordbased search paradigm. While traditional database management systems offer powerful query languages, they do not allow keyword-based search. In this paper, we discuss DBXplorer, a system that enables keywordbased search in relational databases. DBXplorer has been implemented using a commercial relational database and web server and allows users to interact via a browser front-end. We outline the challenges and discuss the implementation of our system including results of extensive experimental evaluation. 1.
DBXplorer enabling keyword search over relational databases.
While relational database systems offer powerfifl structured query languages such as SQL, there is no support for keyword search over databases. The simplicity of keyword search as a querying paradigm offers compelling values for data exploration. Specifically, keyword search does not require a priori knowledge of the schema. The above is significant as much information in a corporation is increasingly being available at its intranet. However, it is unrealistic to expect users who would browse and query such information to have detailed knowledge of the schema of available databases. Therefore, just as keyword search and classification hierarchies complement each other for document search, keyword search over databases can be effective. 2. Overview of DBXplorer We present DBXplorer, a system that enables keyword search over SQL databases. Technical details of our system may be found in [4]. Given a set of query keywords, our system returns all rows (either from single tables or by joining tables connected by foreign-key joins) such that each row contains all keywords. DBA ~1 Publish k r I Populate Search I ~ symbol table
Optimally computing a shortest weakly visible line segment inside a simple polygon.
A simple polygon is said to be weakly internally visible from a line segment lying inside it if every point on the boundary of the polygon is visible from some point on the line segment. In this paper, we present an optimal linear-time algorithm for the following problem: Given a simple polygon, either compute a shortest line segment from which the polygon is weakly internally visible, or report that the polygon is not weakly internally visible.
Overcoming Limitations of Sampling for Aggregation Queries.
We study the problem of approximately answering aggregation queries using sampling. We observe that uniform sampling performs poorly when the distribution of the aggregated attribute is skewed. To address this issue, we introduce a technique called outlier-indexing. Uniform sampling is also ineffective for queries with low selectivity. We rely on weighted sampling based on workload information to overcome this shortcoming. We demonstrate that a combination of outlier-indexing with weighted sampling can be used to answer aggregation queries with significantly reduced approximation error compared to either uniform sampling or weighted sampling alone. We discuss the implementation of these techniques on Microsoft’s SQL Server, and present experimental results that demonstrate the merits of our techniques. 1
A Robust
A general nonparametric technique is proposed for the analysis of a complex multimodal feature space and to delineate arbitrarily shaped clusters in it. The basic computational module of the technique is an old pattern recognition procedure, the mean shift. We prove for discrete data the convergence of a recursive mean shift procedure to the nearest stationary point of the underlying density function and thus its utility in detecting the modes of the density. The equivalence of the mean shift procedure to the Nadaraya–Watson estimator from kernel regression and the robust M-estimators of location is also established. Algorithms for two low-level vision tasks, discontinuity preserving smoothing and image segmentation are described as applications. In these algorithms the only user set parameter is the resolution of the analysis, and either gray level or color images are accepted as input. Extensive experimental results illustrate their excellent performance.
Time Series Similarity Measures and Time Series Indexing.

Lower bounds for computing geometric spanners and approximate shortest paths.
We consider the problems of constructing geometric spanners, possibly containing Steiner points, for sets of points in the d-dimensional space IR  d  , and constructing spanners and approximate shortest paths among a collection of polygonal obstacles in the plane. The complexities of these problems are shown to be \Omega\Gamma n log n) in the algebraic computation tree model. Since O(n log n)-time  algorithms are known for solving these problems, our lower bounds are tight up to a constant factor. 1 Introduction  Geometric spanners are data structures that approximate the complete graph on a set of points in the d-dimensional space IR  d  , in the sense that the shortest path (based on such a spanner) between any pair of given points is not more than a factor of t longer than the distance between the points in IR  d  . Let ø be a fixed constant such that 1  ø  1. Throughout this paper, we measure distances between points in the d-dimensional space IR  d  with the L ø -metric, where d  ...


Context%2DBased Similarity Measures for Categorical Databases.

A lower bound for approximating the geometric minimum weight matching.
Given a set S of 2n points in R  d  , a perfect matching of S is a set of n edges such that each point of S is a vertex of exactly one edge. The weight of a perfect matching is the sum of the Euclidean lengths of all edges. Rao and Smith have recently shown that there is a constant r ? 1, that only depends on the dimension d, such that a perfect matching whose weight is less than or equal to r times the weight of a minimum weight perfect matching can be computed in O(n log n) time. We show that this algorithm is optimal in the algebraic computation tree model.  Keywords: Minimum weight matching, lower bounds, computational geometry. 1 Introduction  Let S be a set of 2n points in R  d  , where d  1 is a (small) constant. We consider sets of edges having the points of S as vertices. Such a set M is called a perfect matching of S, if each point of S is a vertex of exactly one edge in M . In other words, a perfect matching is a partition of S into n  subsets of size two. The weight wt(M) o...
Rule Discovery from Time Series.
We consider the problem of finding rules relating patterns  in a time series to other patterns in that series,  or patterns in one series to patterns in another series.  A simple example is a rule such as &#034;a period  of low telephone call activity is usually followed by a  sharp rise in call volume&#034;. Examples of rules relating  two or more time series are &#034;if the Microsoft stock  price goes up and Intel falls, then IBM goes up the  next day,&#034; and &#034;if Microsoft goes up strongly for one  day, then declines strongly on the next day, and on  the same days Intel stays about level, then IBM stays  about level.&#034; Our emphasis is in the discovery of local  patterns in multivariate time series, in contrast to traditional  time series analysis which largely focuses on  global models. Thus, we search for rules whose conditions  refer to patterns in time series. However, we do  not want to define beforehand which patterns are to be  used; rather, we want the patterns to be formed from  the data in t...
Similarity of Attributes by External Probes.
In data mining, similarity or distance between attributes is one of the central notions. Such a notion can be used to build attribute hierarchies etc. Similarity metrics can be user-defined, but an important problem is defining similarity on the basis of data. Several methods based on statistical techniques exist. For defining the similarity between two attributes A and B  they typically consider only the values of A and B, not the other attributes. We describe how a similarity notion between attributes can be defined by considering the values of other attributes. The basic idea is that in a 0/1 relation r, two attributes A and B are similar if the subrelations oe A=1 (r) and oe B=1 (r) are similar. Similarity between the two relations is defined by considering the marginal frequencies of a selected subset of other attributes. We show that the framework produces natural notions of similarity. Empirical results on the Reuters-21578 document dataset show, for example, how natural classif...
The visibility graph contains a bounded%2Ddegree spanner.
Given a collection of polygonal obstacles with n vertices on the place, and any t ? 1, we present an O(n log n) time algorithm that constructs a bounded-degree t-spanner of the visibility graph, without first having to construct the visibility graph.  1 Introduction  An Euclidean graph is defined as a graph whose vertices are points in k-dimensional space, edges are line segments joining pairs of points, and edge weights are from the underlying distance metric, typically the L 2 metric. If all edges are present, the graph is a complete Euclidean graph, otherwise it is a non-complete Euclidean graph. A well-known example of a non-complete Euclidean graph is the visibility graph, defined as follows. Consider a scenario where we are given a collection of pairwise disjoint polygons on the plane. This frequently arises in motion planning problems, where the polygons represent obstacles in a cluttered workspace within which a point robot has to navigate. Consider a graph over the polygon ver...
Episode Matching.
. Given two words, text T of length n and episode P of length  m, the episode matching problem is to find all minimal length substrings of text T that contain episode P as a subsequence. The respective optimization problem is to find the smallest number w, s.t. text T has a subword of length w which contains episode P . In this paper, we introduce a few efficient off-line as well as on-line algorithms for the entire problem, where by on-line algorithms we mean algorithms which search from left to right consecutive text symbols only once. We present two alphabet independent algorithms which work in time O(nm). The off-line algorithm operates in O(1) additional space while the on-line algorithm pays for its property with O(m) additional space. Two other on-line algorithms have subquadratic time complexity. One of them works in time O(nm= log m) and O(m) additional space. The other one gives a time/space trade-off, i.e., it works in time O(n +  s +nm log log s= log(s=m)) when additional s...
Finding Similar Time Series.

Time%2DSeries Similarity Problems and Well%2DSeparated Geometric Sets.
Given a pair of nonidentical complex objects, defining (and determining) how similar they are to each other is a nontrivial problem. In data mining applications, one frequently needs to determine the similarity between two time series. We analyze a model of time-series similarity that allows outliers, and different scaling functions. We present deterministic and randomized algorithms for computing this notion of similarity. The algorithms are based on nontrivial tools and methods from computational geometry. In particular, we use properties of families of well-separated geometric sets. The randomized algorithm has provably good performance and also works extremely efficiently in practice.  1 Introduction  Being able to measure the similarity between objects is a crucial issue in many data retrieval and data mining applications; see [9] for a general discussion on similarity queries. Typically, the task is to define a function  Sim(X;Y ), where X and Y are two objects of a certain class...
On the Complexity of Approximating Euclidean Traveling Salesman Tours and Minimum Spanning Trees.
We consider the problems of computing r-approximate traveling salesman tours and r-approximate minimum spanning trees for a set of n points in IR  d  , where d  1 is a constant. In the algebraic computation tree model, the complexities of both these problems are shown to be \Theta(n log n=r), for all n and r  such that r ! n and r is larger than some constant. In the more powerful model of computation that additionally uses the floor function and random access, both problems can be solved in O(n) time if r = \Theta(n  1\Gamma1=d  ). 1 Introduction  The Traveling Salesman Problem (TSP ) is one of the best known combinatorial optimization problems. In the geometric version of this problem, we are given a set S of  n points in IR  d  , where d  1 is a constant. A tour is a closed path that visits each point of S exactly once and returns to its starting point. Each edge of such a tour has a length that is equal to the Euclidean distance between its endpoints. The length of a tour is the su...
LR%2Dvisibility in Polygons.

On the Complexity of Optimization Problems for 3%2Ddimensional Convex Polyhedra and Decision Trees.
We show that several well-known optimization problems involving 3-dimensional convex polyhedra and decision trees are NP-hard or NP-complete. One of the techniques we employ is a linear-time method for realizing a planar 3-connected triangulation as a convex polyhedron, which may be of independent interest.  Key words: Convex polyhedra, approximation, Steinitz&#039;s theorem, planar graphs, art gallery theorems, decision trees. 1 Introduction  Convex polyhedra are fundamental geometric structures (e.g., see [20]). They are the product of convex hull algorithms, and are key components for problems in robot motion planning and computer-aided geometric design. Moreover, due to a beautiful theorem of Steinitz [20, 38], they provide a strong link between computational geometry and graph theory, for Steinitz shows that a graph forms the edge structure of a convex polyhedra if and only if it is planar and 3-connected. Unfortunately, algorithmic problems dealing with 3-dimensional convex polyhedra ...
A Fast Algorithm for Constructing Sparse Euclidean Spanners.

Lower Bounds for Computing Geometric Spanners and Approximate Shortest Paths.
We consider the problems of constructing geometric spanners, possibly containing Steiner points, for sets of points in the d-dimensional space IR  d  , and constructing spanners and approximate shortest paths among a collection of polygonal obstacles in the plane. The complexities of these problems are shown to be \Omega\Gamma n log n) in the algebraic computation tree model. Since O(n log n)-time  algorithms are known for solving these problems, our lower bounds are tight up to a constant factor. 1 Introduction  Geometric spanners are data structures that approximate the complete graph on a set of points in the d-dimensional space IR  d  , in the sense that the shortest path (based on such a spanner) between any pair of given points is not more than a factor of t longer than the distance between the points in IR  d  . Let ø be a fixed constant such that 1  ø  1. Throughout this paper, we measure distances between points in the d-dimensional space IR  d  with the L ø -metric, where d  ...

Planar Spanners and Approximate Shortest Path Queries among Obstacles in the Plane.
Abstract. We consider the problem of finding an obstacle-avoiding path between two points s and t in the plane, amidst a set of disjoint polygonal obstacles with a total of n vertices. The length of this path should be within a small constant factor c of the length of the shortest possible obstacle-avoiding s-t path measured in the Lv-metric. Such an approximate shortest path is called a c-short path, or a short path with stretch]actor c. The goal is to preprocess the obstacle-scattered plane by creating an efficient data structure that enables fast reporting of a c-short path (or its length). In this paper, we give a family of algorithms for the above problem that achieve an interesting trade-off between the stretch factor, the query time and the preprocessing bounds. Our main results are algorithms that achieve logarithmic length query time, after subquadratic time and space preprocessing. 1
On the Complexity of Approximating Euclidean Traveling Salesman Tours and Minimum Spanning Trees.
We consider the problems of computing r-approximate traveling salesman tours and r-approximate minimum spanning trees for a set of n points in IR  d  , where d  1 is a constant. In the algebraic computation tree model, the complexities of both these problems are shown to be \Theta(n log n=r), for all n and r  such that r ! n and r is larger than some constant. In the more powerful model of computation that additionally uses the floor function and random access, both problems can be solved in O(n) time if r = \Theta(n  1\Gamma1=d  ). 1 Introduction  The Traveling Salesman Problem (TSP ) is one of the best known combinatorial optimization problems. In the geometric version of this problem, we are given a set S of  n points in IR  d  , where d  1 is a constant. A tour is a closed path that visits each point of S exactly once and returns to its starting point. Each edge of such a tour has a length that is equal to the Euclidean distance between its endpoints. The length of a tour is the su...
Constructing Degree%2D3 Spanners with Other Sparseness Properties.
Let V be any set of n points in k-dimensional Euclidean space. A subgraph of the complete Euclidean graph is a t-spanner if for any ~ and ~ in V, the length of the shortest path from u to v in the spanner is at most t times d(~, ~). We show that for any 5&gt; 1, there exists a polynomial-time constructihle t-spanner (where ~ is a constant that depends only on 5 and k) with the following properties. Its maximum degree is 3, it has at most n 9 6 edges, and its total edge weight is comparable to the minimum spanning tree of V (for/ ~ &lt; 3 its weight is O(1). wt(MgT), and for k&gt; 3 its weight is O(log n). wt(MST)). 1
A New Way to Weigh Malnourished Euclidean Graphs.
In this paper, we show that any Euclidean graph over a set V of n points in k-dimensional space that satisfies either the leapfrog property or the isolation property has small weight, i.e., has weight O(1). wt(SMT), where SMT is a Steiner minimal tree of V. Both the leapfrog property as well as the isolation property constrain the way the edges of the graph are configured in space. Our main application is to prove that certain Euclidean graphs known as t-spanners can be constructed with optimal weight of O(1) + wt(SMT), an intriguing open problem that has attracted much attention recently. The main tool in obtaining the above weight bounds is a theorem that proves the existence of long edges in a Steiner minimal tree on a restricted set of points in k-dimensional space. We also generalize this theorem for

On the Complexity of Approximating and Illuminating Three%2DDimensional Convex Polyhedra %28Preliminary Version%29.

New sparseness results on graph spanners.
Let G = (V
Finding All Weakly%2DVisible Chords of a Polygon in Linear Time %28Extended Abstract%29.
Abstract. A chord of a simple polygon P is weaidy-uiaibleffevery point on P is visible from some point on the chord. We give an optimal lineex-time algorithm which computea a/l weakly-visible chords of a es polygon P with n vertices. 1
A Fast Algorithm for Constructing Sparse Euclidean Spanners.

Optimal Linear%2DTime Algorithm for the Shortest Illuminating Line Segment in a Polygon.
Given a simple polygon, we present an optimal linear-time algorithm that computes the shortest illuminating line segment, if one exists; else it reports that none exists. This solves an intriguing open problem by improving the O(n log n)-time algorithm [Ke87] for computing such a segment. 1
Finding all Weakly%2DVisible Chords of a Polygon in Linear Time.
Abstract. A chord of a simple polygon P is weaidy-uiaibleffevery point on P is visible from some point on the chord. We give an optimal lineex-time algorithm which computea a/l weakly-visible chords of a es polygon P with n vertices. 1
LR%2Dvisibility in Polygons.

Constructing Degree%2D3 Spanners with Other Sparseness Properties.
Let V be any set of n points in k-dimensional Euclidean space. A subgraph of the complete Euclidean graph is a t-spanner if for any ~ and ~ in V, the length of the shortest path from u to v in the spanner is at most t times d(~, ~). We show that for any 5&gt; 1, there exists a polynomial-time constructihle t-spanner (where ~ is a constant that depends only on 5 and k) with the following properties. Its maximum degree is 3, it has at most n 9 6 edges, and its total edge weight is comparable to the minimum spanning tree of V (for/ ~ &lt; 3 its weight is O(1). wt(MgT), and for k&gt; 3 its weight is O(log n). wt(MST)). 1
Optimally Sparse Spanners in 3%2DDimensional Euclidean Space.
Let V be a set of n points in 3-dimensional Euclidean space. A subgraph of the complete Euclidean graph is a t-spanner if for any u and v in V, the length of the shortest path from u to v in the spanner is at most t times d(u, v). We show that for any t&gt; 1, a greedy algorithm produces a t-spanner with O(n) edges, and total edge weight O(1). tot(it4ST), where MST is a minimum spanning tree of V. 1
On Sparse Spanners of Weighted Graphs.
ABSTRACT. Given a graph G, a subgraph G ~ is a t-spanner of G, if for every u, v E V, the distance from u to v in G I is at most t times longer than the distance in G. In this paper we give a very simple algorithm for constructing sparse spanners for arbitrary weighted graphs. We then apply this algorithm to obtain specific results for planar graphs and Euclidean graphs. We discuss the optimality of our results and present several nearly matching lower bounds. 1.
New Sparseness Results on Graph Spanners.
Let G = (V
Geometric Searching and Link Distance %28Extended Abstract%29.
Given n orthogonal line segments on the plane, their intersection graph is defined such that each vertex corresponds to a segment, and each edge corresponds to a pair of intersecting segments. Although this graph can have f~(n 2) edges, we show that breadth first search can be accomplished in O(n log n) time and O(n) space. As an application, we show that the minimum link rectilinear path between two points s and t amidst rectilinear polygonal obstacles can be computed in O(nlog n) time and O(n) space, which is optimal. We mention other related results in the paper. 1
Minimum Vertex Hulls for Polyhedral Domains.
In this paper we investigate several variations of the following problem: Given a collection of pairwise disjoint polygons and their spatial positions in the plane, cover each with a polygonal hull such that (i) the hulls are pairwise disjoint, and
Geometric Searching and Link Distance %28Extended Abstract%29.
Given n orthogonal line segments on the plane, their intersection graph is defined such that each vertex corresponds to a segment, and each edge corresponds to a pair of intersecting segments. Although this graph can have f~(n 2) edges, we show that breadth first search can be accomplished in O(n log n) time and O(n) space. As an application, we show that the minimum link rectilinear path between two points s and t amidst rectilinear polygonal obstacles can be computed in O(nlog n) time and O(n) space, which is optimal. We mention other related results in the paper. 1
Minimum Vertex Hulls for Polyhedral Domains.
In this paper we investigate several variations of the following problem: Given a collection of pairwise disjoint polygons and their spatial positions in the plane, cover each with a polygonal hull such that (i) the hulls are pairwise disjoint, and
Generating Sparse Spanners for Weighted Graphs.
ABSTRACT. Given a graph G, a subgraph G ~ is a t-spanner of G, if for every u, v E V, the distance from u to v in G I is at most t times longer than the distance in G. In this paper we give a very simple algorithm for constructing sparse spanners for arbitrary weighted graphs. We then apply this algorithm to obtain specific results for planar graphs and Euclidean graphs. We discuss the optimality of our results and present several nearly matching lower bounds. 1.
Which Triangulations Approximate the Complete Graph%3F.
Abstract. Chew and Dobkin et. al. have shown that the Delaunay triangulation and its variants are sparse approximations of the complete graph, in that the shortest dis-tance between two sites within the triangulation is bounded by a constant multiple of their Euclidean separation. In this paper, we show that other classical triangulation algorithms, such as the greedy triangulation, and more notably, the minimum weight triangulation, also approximate the complete graph in this sense. We also design an algorithm for constructing extremely sparse (nontriangular) planar graphs that approx-imate the complete graph. We define a sufficiency condition and show that any Euclidean planar graph con-structing algorithm which satisfies this condition always produces good approximations of the complete graph. This condition is quite general because it is satisfied by all the tri-angulation algorithms mentioned above, and probably by many other graph algorithms as well. We thus partially answer the question posed by the title. From a theoretical standpoint, our results are interesting because we prove non-trivial properties of minimum weight triangulations, of which little is currently known. From a practical standpoint, the graph algorithms we consider are good alternatives to the Delaunay triangulation, particularly when designing a sparse network under se-vere constraints on the total edge length. Finally, our general approach may help in identifying or designing other algorithms for constructing sparse networks. 1.
